package binaryTree;

import java.util.ArrayList;

import utils.binaryTreeUtil.TreeNode;

public class flatten {
    //法一：前序遍历+list  
    ArrayList<TreeNode> list = new ArrayList<>();
    public void flatten1(TreeNode root) {
        if (root==null||(root.left==null&&root.right==null)) {
            return;
        }
        preOrder(root);
        TreeNode curr= root;
        for(int i=1;i<list.size();i++){
            TreeNode node = list.get(i);
            curr.right=node;
            curr.left=null;
            curr=node;
        }
    }
    public void preOrder(TreeNode node){
        if (node==null) {
            return;
        }
        list.add(node);
        preOrder(node.left);
        preOrder(node.right);
    }
    //法二：在oh空间复杂度实现，其实本质就是一个链接过程，类似链表，就是迭代
    //因为递归也要用到栈，也是开销
    TreeNode curr=null; 
    public void flatten2(TreeNode root) {
        //结果先都放到左节点，然后再放到右节点
        preOrder2(root);
        curr=root;
        while (curr!=null) {
            TreeNode next = curr.left;
            curr.left=null;
            curr.right=next;
            curr=next;
        }
    }
    public void preOrder2(TreeNode node){
        if (node==null) {
            return;
        }
        if (curr==null) {
            curr=node;
        }else{
            curr.left=node;
            curr=node;
        }
        preOrder2(node.left);
        preOrder2(node.right);
    }
    public static void main(String[] args) {
        
    }
}
